// 动态规划 - 核心 5 步：
// 1. 确定状态表示 - 根据 题目要求，经验，发现重复子问题 确定状态表示
// 2. 推导状态转移方程: dp[i] = ?
//    用 之前的状态 或者 之后的状态 推导当前的状态（根据最近一步划分问题）
// 3. 初始化：保证填表时不越界
// 4. 确定填表顺序：填写当前状态值的时候，所需状态的值已经计算过了
// 5. 返回值：结合题目要求 + 状态表示

// 经典题目：斐波那契数列模型，路径问题

// 技巧：
// dp[] 表多开一个长度，处理数组越界及初始化复杂的问题
// dp[][] 表多开一行，多开一列
// 结合滚动数组优化 - 注意赋值顺序

// 例题 1：
// 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
// 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
//
//        问总共有多少条不同的路径？
//
//        示例 1：
//
//
//        输入：m = 3, n = 7
//        输出：28
//        示例 2：
//
//        输入：m = 3, n = 2
//        输出：3
//        解释：
//        从左上角开始，总共有 3 条路径可以到达右下角。
//        1. 向右 -> 向下 -> 向下
//        2. 向下 -> 向下 -> 向右
//        3. 向下 -> 向右 -> 向下
//        示例 3：
//
//        输入：m = 7, n = 3
//        输出：28
//        示例 4：
//
//        输入：m = 3, n = 3
//        输出：6
//
//
//        提示：
//
//        1 <= m, n <= 100
//        题目数据保证答案小于等于 2 * 109

// 解题思路：
// 思路 1：
// dp[i][j] 表示从 i,j 位置出发到达右下角的路径数
// dp[][] = new int[m + 1][n + 1], 多开一行，多开一列
// dp[i][j] = dp[i][j + 1] + dp[i + 1][j]
// dp[m - 1][n - 1] = 1
// 从下往上填表，每一行从右往左填
// 返回 dp[0][0]

// 思路 2：
// dp[i][j] 表示从 1,1 出发到达 i,j 位置的路径数
// dp[][] = new int[m + 1][n + 1], 多开一行，多开一列
// dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
// dp[1][1] = 1
// 从上往下填表，每一行从左往右
// 返回 dp[m][n]

public class UniquePaths {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m + 1][n + 1];

        dp[m][n - 1] = 1;

        for(int i = m - 1; i >= 0; i--){
            for(int j = n - 1; j >= 0; j--){
                dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
            }
        }

        return dp[0][0];
    }

    public int uniquePaths2(int m, int n) {
        int[][] dp = new int[m + 1][n + 1];

        dp[0][1] = 1;

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m][n];
    }
}
